package com.zl.learning.arithmetic.sort;

import java.util.Arrays;

/**
 * Created by sunqianqian on 2015/3/16.
 * <p/>
 * 冒泡排序.时间复杂度O(n^2)
 * 效率低,n小时使用
 * <p>
 * 冒泡排序要对一个列表多次重复遍历。它要比较相邻的两项，并且交换顺序
 * 排错的项。每对 列表实行一次遍历，就有一个最大项排在了正确的位置。大
 * 体上讲，列表的每一个数据项都会在 其相应的位置 “冒泡”。如果列表有
 * n 项，第一次遍历就要比较 n-1 对数据。需要注意，一旦列 表中最大(按照
 * 规定的原则定义大小)的数据是所比较的数据对中的一个，它就会沿着列表一
 * 直 后移，直到这次遍历结束。
 */
public class BubbleSort {

    public static int[] a = {3, 7, 5, 2, 10, 9, 4, 6};

    /**
     * 冒泡排序
     *
     * @param a
     * @return
     */
    public static int[] bubbleSort(int[] a) {
        int temp;
        int time = 1;
        int len = a.length;
        //第一层循环,循环次数为数组长度
        for (int i = 0; i < len; i++) {
            //每一次内循环相邻比较,大数往后交换,都会把a[0]..a[len-i-1]中最大的数字放到a[len-i-1]
            for (int j = 0; j < len - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
            System.out.println("第" + (time++) + "次外循环,数组此时为:" + Arrays.toString(a));
        }
        return a;
    }

    /**
     * 冒泡排序优化
     * 设置flag表示是否已经发生交换
     * 若没发生交换说明 排序已完成
     */
    public static int[] bubbleSort2(int[] a) {
        int temp;
        int time = 1;
        int len = a.length;
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int j = 0; j < len - 1; j++) {
                if (a[j] > a[j + 1]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = true;
                }
            }
            System.out.println("第" + (time++) + "次外循环,数组为:" + Arrays.toString(a));
        }
        return a;
    }

    /**
     * 冒泡排序优化
     * 记下最后发生交换的位置,此位置之后的元素有序
     * 下一次从开始到这个位置排序就好了
     */
    public static int[] bubbleSort3(int[] a) {
        int time = 1;
        int temp;
        int len;
        int index = a.length - 1;
        while (index > 0) {
            len = index;
            index = 0;
            for (int i = 0; i < len; i++) {
                if (a[i] > a[i + 1]) {
                    temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    index = i;
                }
            }
            System.out.println("第" + (time++) + "次外循环,数组为:" + Arrays.toString(a));
        }
        return a;
    }

    public static void bubbleSort4(int[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) {
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                }
            }
        }
    }


    public static void main(String[] args) {
        System.out.println(Arrays.toString(a));
        bubbleSort3(a);
        System.out.println(Arrays.toString(a));
    }

}
